#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define INFINITY 100000000

    int sift[10010];
    int g[1300][1300]; 
    int dist[1300], mark[1300];
    int n;
    int a, b;
    int Ncase;
    
int Dijkstra(int st, int ed)
{
    int i, j, k, p;
    memset(mark, 0, sizeof(mark));
    for (i=0; i<n; i++) dist[i] = g[st][i];
    
    mark[st] = 1;
    for (i=1; i<n; i++) {
        p = 0; while (mark[p] && p<n) p++;
        /*/debug
        printf("p=%d\n", p);
        //debug*/
        if (p>=n) break;
        for (j=p+1; j<n; j++) if (!mark[j] && dist[j]<dist[p]) p=j;
        mark[p] = 1;
        for (j=0; j<n; j++) 
        {
            /*/debug
            if (j==ed)
                printf("%d = %d + %d\n", dist[j], dist[p], g[p][j]);
            //debug*/
            if (!mark[j] && dist[j]>dist[p]+g[p][j]) {
            /*/debug
            printf("%d = %d + %d\n", dist[j], dist[p], g[p][j]);
            //debug*/
            dist[j] = dist[p] + g[p][j];
            }    
        }    
    }
    if (dist[ed]==INFINITY) return -1; else return dist[ed];
}
    
int main()
{
    int i, j, k, p;
    char num[10], newnum[10];
    int v1, v2;
    int st, ed;
    
    //build prime
    memset(sift, 0, sizeof(sift));
    n = 0; sift[2] = n++;
    for (i=4; i<10000; i+=2) sift[i] = -1;
    for (i=3; i<10000; i+=2) if (!sift[i]) {
        sift[i] = n++;
        for (j=i+i; j<10000; j+=i) sift[j] = -1;
    } 
    
    // relabel from >= 1000
    for (i=0; i<1000; i++) sift[i] = -1;
    n=0; 
    for (i=1000; i<10000; i++) if (sift[i] >= 0)
        sift[i] = n++;
        
    //build graph
    for (i=0; i<n; i++)
        for (j=0; j<n; j++)
            g[i][j]=INFINITY;
    for (i=1000; i<10000; i++) if (sift[i] >= 0) {
        v1 = sift[i];
        sprintf(num, "%d", i);
        /*/debug
        printf("%s\n", num);
        //debug*/
        for (j=0; j<4; j++) {
            strcpy(newnum, num);
            for (k=(j>0?'0':'1'); k<='9'; k++) {
                newnum[j] = k;
                /*/debug
                printf("\t%s\n", newnum);
                //debug*/
                sscanf(newnum, "%d", &p);
                v2 = sift[p];
                if (v2>=0) {
                    if (v1==v2) g[v1][v2] = 0;
                    else g[v1][v2] = g[v2][v1] = 1;
                }
            }
        }    
    }
    
    // start dijkstra
    scanf("%d", &Ncase);
    while (Ncase--) {
        scanf("%d%d", &a, &b);
        st = sift[a]; ed = sift[b];
        int ans = Dijkstra(st, ed);
        if (ans>=0) printf("%d\n", ans); else printf("Impossible\n");
    }
}

